package com.itheima.sort;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr ={6,1,2,7,9,3,4,5,10,8};
     quickSort(arr,0,arr.length-1);
     Print(arr);
    }

    public static void quickSort(int[] arr,int i,int j){
        if (i>=j){
            return;
        }
        int pivot = arr[i];
        int start = i;
        int end = j;

        while (end>start) {
            //end从后往前找比pivot小的元素
            while (end>start && arr[end]>=pivot){
                end--;
            }
            //start从前往后找比pivot大的元素
            while (end>start && arr[start]<=pivot){
                start++;
            }
          //交换start与end所在元素的位置
            int temp =arr[start];
            arr[start] =arr[end];
            arr[end] =temp;
        }
        //交换start所在元素与pivot的值
        int temp = arr[i];
        arr[i] =arr[start];
        arr[start] = temp;

        quickSort(arr,i,start-1);
        quickSort(arr,start+1,j);

    }
    private static void Print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
